package random;

import java.util.Deque;
import java.util.LinkedList;
import java.util.TreeMap;

/**
 * 132模式
 * <p>
 * 给你一个整数数组 nums，数组中共有 n 个整数。132模式的子序列 由三个整数 nums[i]、nums[j]和nums[k] 组成
 * 并同时满足：i<j<k 和 nums[i]<nums[k]<nums[j]
 * 如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。
 */

public class L456_单调栈 {

    public static void main(String[] args) {
        System.out.println(find132pattern(new int[]{3,5,0,1,2,4}));
    }

    /*
    枚举法3 （维护中间的数）
    就是维护右边列表的数组
    找到右边比左边大并且小于正在枚举的中间这个数，就返回true 否则返回false
    使用红黑树进行维护右边列表的数
     */
    public static boolean find132pattern(int[] nums) {

        int n = nums.length;
        if (n < 3) {
            return false;
        }

        // 左侧最小值
        int leftMin = nums[0];
        // 右侧所有元素
        TreeMap<Integer, Integer> rightAll = new TreeMap<Integer, Integer>();

        for (int k = 2; k < n; ++k) {
            rightAll.put(nums[k], rightAll.getOrDefault(nums[k], 0) + 1);
        }

        for (int j = 1; j < n - 1; ++j) {
            if (leftMin < nums[j]) {
                Integer next = rightAll.ceilingKey(leftMin + 1);
                if (next != null && next < nums[j]) {
                    return true;
                }
            }
            leftMin = Math.min(leftMin, nums[j]);
            rightAll.put(nums[j + 1], rightAll.get(nums[j + 1]) - 1);
            if (rightAll.get(nums[j + 1]) == 0) {
                rightAll.remove(nums[j + 1]);
            }
        }

        return false;

      /*  作者：LeetCode-Solution
        链接：https://leetcode-cn.com/problems/132-pattern/solution/132mo-shi-by-leetcode-solution-ye89/
        来源：力扣（LeetCode）
        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
    }


    /*
    枚举1
    从右往左进行遍历
    我们使用一种数据结构维护所有遍历过的元素，它们作为 2 的候选元素。每当我们遍历到一个新的元素时，就将其加入数据结构中
    在遍历到一个新的元素的同时，我们可以考虑其是否可以作为 3。如果它作为 3，那么数据结构中所有严格小于它的元素都可以作为 2，
    我们将这些元素全部从数据结构中移除，并且使用一个变量维护所有被移除的元素的最大值。
    这些被移除的元素都是可以真正作为 2 的，并且元素的值越大，那么我们之后找到 1 的机会也就越大

   使用单调栈数据结构！
     */
    public boolean find132pattern1(int[] nums) {
        int n = nums.length;
        Deque<Integer> candidateK = new LinkedList<>();
        candidateK.push(nums[n - 1]);
        int maxK = Integer.MIN_VALUE;

        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] < maxK) {
                return true;
            }
            while (!candidateK.isEmpty() && nums[i] > candidateK.peek()) {
                maxK = candidateK.pop();
            }
            if (nums[i] > maxK) {
                candidateK.push(nums[i]);
            }
        }

        return false;
    }
/*
    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/132-pattern/solution/132mo-shi-by-leetcode-solution-ye89/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
}
